• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Electronic circuit stops the calculation of the sines and cosines of multiples of an angle that allows to efficiently implement the computation of the twiddle factors of the Fourier transform. (Machine-translation by Google Translate, not legally binding)
    公开号:ES2663168A1
    申请号:ES201600865
    申请日:2016-10-10
    公开日:2018-04-11
    发明作者:David GUERRERO MARTOS；Julián VIEJO CORTÉS；Paulino RUIZ DE CLAVIJO VÁZQUEZ；Jorge JUAN CHICO；Manuel Jesús BELLIDO DÍAZ；Alejandro MILLÁN CALDERÓN；Enrique OSTÚA ARANGÜENA；Jose Ignacio VILLAR DE OSSORNO；Juan QUIRÓS CARMONA；Alejandro MUÑOZ RIVERA
    申请人:Universidad de Sevilla；
    IPC主号:
    专利说明:

    5
    10
    fifteen
    twenty
    25
    30


    Digital electronic circuit for the calculation of sines and cosines of multiples of an angle
    Object of the invention
    The present invention aims at a digital electronic circuit that calculates the twiddle coefficients of the Fourier transform using a subcircuit that calculates the sines and cosines of integer multiples of a particular angle comprising semiconductor memories whose total number of inputs is of the order of Logarithm of the length of the transform. This implies considerable savings in area (components) and memory consumption in applications where the data stream is long.
    It has its application in the area of electronic technology, specifically, in digital signal processing.
    State of the art
    Among the main objectives of the designers of digital electronic circuits are the reduction of the area occupied by them as well as the reduction of their energy consumption and the increase in their speed. The reduction of area allows to reduce the production costs of the chips and generally leads to a reduction in consumption. The latter is especially important in portable equipment powered by batteries in order to increase their autonomy. Many of these teams integrate circuits that calculate sines and / or cosines of multiples of an angle. A notable example is the circuits that implement the fast Fourier transform. They require a series of complex coefficients (called twiddle or pivot) whose values are obtained from the corresponding sine / cosine pairs of certain multiples of the same angle. Since the calculation of trigonometric functions is costly in time, in hardware implementations of the transform where the speed is critical, these values are precalculated in direct access memories (usually of the ROM type). These memories can have a large number of positions as many coefficients are required as samples have the series. This is a serious penalty in area and hardware consumption
    5
    10
    fifteen
    twenty
    25
    30
    35
    of calculation of long sequence transforms, the memory size being very large compared to the rest of the components (1).
    Therefore, several ways of reducing the number of positions required have been proposed:
    - D. Cohen showed that a number of positions equal to half the number of samples (2) was sufficient.
    - Y. Ma, L. Wanhammar, Y. Chang and K. K. Parhi reduced the number of positions to a quarter by storing only the angle coefficients in a quarter circumference interval. The rest is obtained easily and quickly by means of simple trigonometric relationships that only need to permute and change the sign of the components of the stored values (3) and (4).
    - M. Hasan and T. Arslan reduced the number of positions to just over an eighth of the number of samples by storing only the coefficients in a range of one eighth of circumference. Again, the remaining coefficients can be quickly calculated from them by applying trigonometric ratios (5).
    - T. Sansaloni, A. Pérez-Pascual, V. Torres and J. Valls reduced the number of positions to exactly one eighth of the number of samples using specific hardware to detect and treat the coefficients whose real / imaginary part has a
    magnitude equal to. This allows to avoid the problems derived from complementing a semiconductor memory whose size is not a power of 2 (6).
    However, all these improvements require a memory of a number of positions that grows linearly with the number of samples. This is inconvenient in applications where the data sequence is long such as PLC (7) or DVB-T2
    (8) (with lengths of the order of 2A13 and 2A15 respectively) or very long as is the case of applications based on photon counting (9) or the use of radio telescopes (10) (with lengths of the order of 2A27 and 2A30 respectively).
    References
    (1) O. Gustafsson, “Analysis of Twiddle Factor Memory Complexity of Radix-2 'Pipelined FFTs’ Conference Record of the Forty-Third Asilomar Conference on Signáis, Systems and Computers, 2009, pages 217-220
    (2) “Simplified control of FFT hardware” IEEE Trans. Acoust Speech Signa! Process, pages 577-579,1976
    (3) “Efficient FFT implementation using digit-serial arithmetic’>, IEEE Workshop on Signal Processing Systems, pages 645-653, 1999
    5
    10
    fifteen
    twenty
    25
    30
    35
    (4) “Hardware efficient control of memory addressing for high performance FFT processors", IEEE Trans. Signal Process, pages 917-921, 2000
    (5) “Scheme for reducing size of coefficient memory in FFT processor”, Electronics Letters, pages 907-911, February 14, 2002
    (6) “Scheme for Reducing the Storage Requirements of FFT Twiddle Factors on FPGAs,” Journal of VLSI Signal Processing, pages 183-187, 2006
    (7) IEEE 1901, "IEEE Standard for Broadband over Power Une Networks: Medium Access Control and Physical Layer Specifications", IEEE Communications Society, 2010.
    (8) "Digital Video Broadcasting (DVB); Frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)", Ref. REN / JTC-DVB-308, ETSI EN 302 755 vi.3.1 , 2012.
    (9) Stanton, R. H., "PhotonCounting - One More Time", The Society for Astronomy! Sciences, 31 st Annual Symposium on Telescope Science, May 22-24, 2012, Big Bear Lake, CA. Society for Astronomical! Sciences, 2012, pp. 177-184.
    (10) Nakahara, H., Nakanishi, H., Sasao, T., "On a Wideband Fast Fourier Trasform for a Radio Telescope", ACM SIGARCH Computer Architecture News, Vol. 40, No. 5, pp. 46-51, December 2012.
    Description of the figures
    Figure 1.- A subcircuit is calculated that calculates the sines and cosines of the multiples of & = 2tt / L = tt / 2 ™ in the interval [0.77 / 4), that is, the powers of the complex e01. The subcircuit is structured in two phases and comprises four small memories (F = 2, D = 2f = 4), called M0, Mu M2 and M2 (1). Each K index memory maintains the coefficients (sine / cosine pairs) of the multiple angles of 2k (P .M2 has only two direction lines (q = 2) and the other three memories (r = 3) have one more line. In total, these ROMs only add up to 28 memory locations, let d be the subcircuit input (11 bits), this calculates the complex in 0 'where n is the number encoded in d. The bits of d are distributed between the address lines of the memories so that each of them provides the sine / cosine pair of a sub-angle ak where n <P = ao + a1 + a2 + ci3. The complex en0 'is obtained by multiplying the outputs of the memories using two levels of complex multipliers ( 2) so that the total delay of the subcircuit is two complex multipliers.
    Figure 2- A circuit is calculated that calculates the Twiddle coefficients of the Fourier transform for samples of length L = 2f following the scheme of T.
    5
    10
    fifteen
    twenty
    25
    30
    35
    Sansaloni In the case of example f = 14. The index of the coefficient to be calculated is encoded at input B = Bf.1Bf.2..B0. The circuit comprises a subcircuit as illustrated in Figure 2 (3). A multiplexer (4a) and an adder (5) are used so that the subcircuit that returns the sines and cosines receives as input Bf.4Bf_5..B0 when Bf.3 = 0, or its complement to two when Bf.3 = 1 A logic gate (6a) checks if bit Bf.3 is worth 1 and the rest of the least significant bits of B are worth 0, in which case the magnitude
    returned for the sine and cosine is 1 / ^ thanks to a pair of multiplexers (4b). In the last stage another logic gate (6b) calculates the EXOR logic operation of Bf.3 and Bf.2. If the value of the EXOR logic operation is 0 a pair of multiplexers (4c) will make the magnitude of the imaginary part and the real part equal to that of the sine and the cosine calculated by the subcircuit (3) respectively. Otherwise the imaginary and real magnitudes will be those of the cosine and the sine respectively. The sign of the real and the imaginary part are easily calculated with simple logic gates (6c) based on Bf.2 and BM.
    Description of the invention
    The invention relates to a digital electronic circuit that calculates the twiddle coefficients of the Fourier transform. Twiddle coefficients are the sine / cosine pairs of the multiple angles of -2tt / L, where L is the length of the sequence on which the transform is applied. That is, the twiddle coefficients are the powers of the e2TTUL complex. To carry it out, a sub-circuit has been devised that calculates the complex at 0 i.e., the sine and cosine of n & 0 being a constant angle and n a coded number in base 2 that is supplied as input. It should be noted that the subcircuit can be used for trigonometric calculation in general and not only for the calculation of twiddle coefficients. The subcircuit consists of the following components:
    • semiconductor memories (usually ROM type)
    • complex multipliers
    • lines that interconnect them in the form of a tree
    Let b be the subcircuit input and E the number of bits of b, N = 2E different angles can be encoded. The subcircuit is structured in a number F of phases with F being no greater than the logarithm in base 2 of E. In total, the subcircuit comprises d = 2F direct access memories that we will call M0, M1t Let the quotient be
    to divide E by d and let r be the rest, from among the memories r will have q + 1 address lines. The rest will have only q address lines. Let lines (Mk) be the number of address lines of each memory k, you have
    5
    10
    fifteen
    twenty
    25
    30
    J-1
    £ lines (Mk) = E
    k = 0
    Each memory position p of the memory Mm will contain the sine and the cosine of the angle
    ^ lines (i íK)
    4> p 2k- °
    In other words, said memory location will contain the complex defined by
    e A (0/7 2
    ME
    ¿T lines (M ^
    i)
    Let b = bE. 1 bE. 2 ■ b1 b0, the input of the subcircuit that encodes the number n, to obtain the sine and cosine of n &, that is, the complex in <pl, is divided b into d sub-chainsSo, Sh Sd.j of line lengths (M0 ), lines (M1), ....! lines {Md.1). Notice that
    n = n02 ° + n 12! lines (M0} + n22 "lines (M0) + lines (M1) + .. + / <M2
    ¡Neas (MO) + lines (M 1) + .. + lines (Md-1)
    where nk denotes the number represented by substring Sk. Therefore we have that n0 = ao + a1 + .. + ad.1 being each angle ak defined by
    ak = <Pnt2
    And lines (M ^
    So the desired value can be calculated using the product
    n @ i a0i a, i ad_, i
    e = e 0 e '..e
    The address lines of each memory Mm are connected to the subentry Sm so that its output provides the complex e * (ami). The eA (n & i) value is calculated by the multipliers from the memory outputs. The multipliers are arranged in parallel so that each phase introduces a delay equal to that of a complex multiplier. In the case of taking the value of the default integer part of log2 (E) for F, at most E memories of no more than two address lines would be available, so that the number of total memory locations will be bounded above by 22E = 4log2 (N). This dimension grows logarithmically with the number of angles N.
    The presented subcircuit can be used to directly calculate the twiddle coefficients of a transform of length L taking 0 = -2jt / L. The number of bits of input E would be the integer part in excess of log2 {L) so that E <2log2 (L). If the number of the default integer part of log2 {E) is taken as the number of phases F, no more than E memories of no more than two address lines would be had, so that the number of total memory locations will be bounded higher by
    5
    10
    fifteen
    twenty
    25
    30
    22E <Qlog2 (L). Although this alone saves a lot of resources compared to the state of the art, if L is power of 2 an even more optimized circuit can be used. The optimized circuit is composed of the following elements:
    • A subcircuit as described in the previous section
    • Five 2: 1 multiplexers
    • An adder
    • A set of logical doors
    This circuit uses a similar scheme to that presented by T. Sansaloni so that cases in which the multiple of 0 corresponds to angles ni4, 377/4, 5 77/4 and 7rr / 4 are detected with a simple logic gate and They are treated separately. The door is limited to checking if bit Bf.3 is worth 1 and the rest of the least significant bits of B are worth 0, in which case the magnitude returned for the sine (imaginary part) and the cosine (part
    real) is 1 / ^ thanks to a pair of multiplexers. Unlike the T. Sansaloni scheme, this circuit does not use a ROM to obtain the sines and cosines of the multiples of 0--2rr / L in the interval (-77 / 4.0), instead a subcircuit as described above to calculate the sine / cosine pairs of the multiples of 0 = 2tt / L in the interval [0.77 / 4). This makes it possible to greatly reduce the memory needed to implement the system. In addition, since the sines and cosines of all angles in the interval [0.77 / 4) are positive, complex multipliers can be implemented using unsigned magnitude multipliers. Let the length of the transform L = 2f be B and B = Bf.1 Bf.2..B0 the input of the optimized circuit that encodes the index of the twiddle coefficient to be calculated, when Bf.3 = 0 the input to the subcircuit that returns the breasts and cosines becomes the same as substring Bf.4Bf.5..B0. Otherwise, the complement to two of said substring is equal. For this, a multiplexer and an adder are used. A logic gate checks if bit Bf.3 is worth 1 and the rest of the least significant bits of B are worth 0, in which case the magnitude returned
    for the sine and cosine it is 1 / ^ thanks to a pair of multiplexers connected to the output of the subcircuit. In the last stage a door calculates the logical operation EXOR of Bf.3 and Bf, 2. If a pair of multiplexers is worth 0 they will make the magnitude of the imaginary part and the real part equal to that of the sine and the cosine calculated by the subcircuit respectively. Otherwise the imaginary and real magnitudes will be those of the cosine and the sine respectively. The sign of the real and the imaginary part is calculated with simple logic gates based on Bf.2 and BM.
    Embodiment of the invention
    As an example, a circuit that calculates the twiddle coefficients of the Fourier transform for sequences of length L = 214. has been made on FPGA (Field Programmable Gate Array). This requires knowing the sines and cosines of the 5 integer multiples of the angle. Q = -2n / L = -n / 2 ™. In the scheme presented by T. Sansaloni, the coefficients corresponding to the angles in the interval (-77 / 4.0) (one eighth of a circle, that is, N = L / 8 = 211 = would be stored in a ROM) 2048) The ROM would have 11 address lines (E = 11) and 2048 memory locations, instead of that ROM the 10 subcircuit of Figure 1 has been used, which calculates the breasts (imaginary part) and cosines (real part) of the multiples of <P = 2tt / L = tt / 213 in the interval [0.77 / 4) using only a total of 28 memory locations. Said subcircuit is used in the circuit of Figure 2 for the calculation of the twiddle coefficients.
    权利要求:
    Claims (2)
    [1]
    5
    10
    fifteen
    twenty
    25
    30
    Claims
    l. Subcircuit that calculates the complex in <p that is, the sine and cosine of n <P where 0 is a constant angle and n a number coded in base 2 that is supplied as an input characterized in that the subcircuit consists of the following components:
    • semiconductor memories (usually ROM type)
    • complex multipliers
    • lines that interconnect them in the form of a tree
    Let b be the subcircuit input and E the number of bits of b, N = 2e different angles can be encoded. The subcircuit is structured in a number F of phases with F being no greater than the logarithm in base 2 of E. In total, the subcircuit comprises d = 2F direct access memories that we will call M0, Mh Md _ f. Let q be the quotient of dividing E by d and let r be the rest, among the d memories r will have q + 1 address lines. The rest will have only q address lines. Let lines (Mk) be the number of address lines of each memory k, you have
    d ~ 1
    ^ lines (MK) = E
    k = o
    Each memory position p of the memory Mm will contain the sine and the cosine of the angle
    ] T Lines (MK)
    0p2 ™
    In other words, said memory location will contain the complex defined by
    0p 2
    ^ lines (A t ^
    i)
    Let b = bE. 1 bE. 2 • • • b1 b0, the input of the subcircuit that encodes the number n, to obtain the sine and cosine of n0, that is, the complex in <pl, is divided into dsubcadenasSo, Sh S <m of Line lengths ( M0), /// 7eas (/ W7), lines {Md.1). Notice that
    n = no2 ° + n12 lines (MO) + n22lines (MO) + lines (M1) + .. + nd .-, 2
    lines (M0) + lines (M1) + .. + lines (Md-1)
    where nk denotes the number represented by substring Sk. Therefore we have that n0 = ao + a1 + .. + ad.1 being each angle ak defined by
    to
    0nk2
    lines
    5
    10
    fifteen
    twenty
    25
    30
    The desired value is calculated using the product ^ ~ e e -e. The address lines of each memory Mm are connected to the sub-entry Sm. Its exit provides the complex eA (ami). The eA (n & i) value is calculated by the multipliers from the memory outputs. The multipliers are arranged in parallel to optimize the speed.
    [2]
    2. A circuit for calculating the twiddle coefficients of a Fourier transform of length L using a subcircuit as described in the preceding claim to calculate the sine / cosine pairs of the multiples of 0 = 2tt / L in the interval [0, rr / 4). Let the length of the transform L = 2f be B and B = Bf.1 Bf-2..B0 the input that encodes the index of the twiddle coefficient to be calculated, characterized in that when Bf.3 = 0 the input to the subcircuit that returns the sines and cosines becomes the same as substring Bf.4Bf.5- Bo. Otherwise, the complement to two of said substring is equal. For this, a multiplexer and an adder are used. A logic gate checks if the Bf bit. 3 is worth 1 and the rest of the least significant bits of B are worth 0, in which case the
    magnitude returned for sine and cosine is 1 / ^ thanks to a pair of multiplexers connected to the output of the subcircuit. In the last stage a door calculates the logical operation EXOR of Bf_3 and Bf_2. If a pair of multiplexers is worth 0 they will make the magnitude of the imaginary part and the real part equal to that of the sine and the cosine calculated by the subcircuit respectively. Otherwise the imaginary and real magnitudes will be those of the cosine and the sine respectively. The sign of the imaginary part is calculated with an inverter whose input is connected to while that of the real part is calculated with an EXOR logic gate whose inputs are connected to Bf.2 and
    类似技术:
    公开号 | 公开日 | 专利标题
    ES2663168A1|2018-04-11|Digital electronic circuit for the calculation of sinuses and cosines of multiples of an angle |
    Oruklu et al.2012|Reduced memory and low power architectures for CORDIC-based FFT processors
    Nguyen et al.2018|A high-performance, resource-efficient, reconfigurable parallel-pipelined FFT processor for FPGA platforms
    Revanna et al.2013|A scalable FFT processor architecture for OFDM based communication systems
    Cılasun et al.2020|Crafft: High resolution fft accelerator in spintronic computational ram
    Paul et al.2014|Low power reconfigurable FP-FFT core with an array of folded DA butterflies
    Langemeyer et al.2011|A FPGA architecture for real-time processing of variable-length FFTs
    Changela et al.2020|FPGA implementation of high-performance, resource-efficient Radix-16 CORDIC rotator based FFT algorithm
    Sung et al.2009|Reconfigurable VLSI architecture for FFT processor
    Györfi et al.2013|Implementing modular FFTs in FPGAs--A basic block for lattice-based cryptography
    Wenqi et al.2010|Design of fixed-point high-performance FFT processor
    Jing et al.2010|A configurable FFT processor
    Karlsson et al.2015|Cost-efficient mapping of 3-and 5-point DFTs to general baseband processors
    Malashri et al.2013|Low power and memory efficient FFT architecture using modified CORDIC algorithm
    Vo-Thi et al.2017|A floating-point FFT Twiddle factor implementation based on adaptive angle recoding CORDIC
    Sun et al.2013|An implementation of FFT processor
    More et al.2013|FPGA implementation of FFT processor using vedic algorithm
    ES2762745B2|2021-11-26|ELECTRONIC DEVICE CALCULATING TRIGONOMETRIC FUNCTIONS AND USES OF THE SAME
    Nakahara et al.2012|On a wideband fast Fourier transform using piecewise linear approximations: Application to a radio telescope spectrometer
    Patle et al.2013|Implementation of Baugh-Wooley Multiplier Based on Soft-Core Processor
    Ramakrishna et al.2016|An efficient and enhanced memory based FFT processor using radix 16 booth with carry skip adder
    Su et al.2010|Low cost VLSI design of a flexible FFT processor
    Shi et al.2011|The design and implementation of reconfigurable multiplier with high flexibility
    ES2762747A1|2020-05-25|ELECTRONIC DEVICE CALCULATOR OF TRIGONOMETRIC FUNCTIONS |
    Lakkadi et al.2017|Radix-4 modular pipeline fast Fourier transform algorithm
    同族专利:
    公开号 | 公开日
    ES2663168B2|2018-08-16|
    WO2018104566A1|2018-06-14|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US7440987B1|2003-02-25|2008-10-21|Qualcomm Incorporated|16 bit quadrature direct digital frequency synthesizer using interpolative angle rotation|
    US20050273483A1|2004-06-04|2005-12-08|Telefonaktiebolaget Lm Ericsson |Complex logarithmic ALU|
    US20140337401A1|2011-12-31|2014-11-13|Institute Of Automation, Chinese Academy Of Sciences|Data access method and device for parallel fft computation|
    ES2762745B2|2018-11-22|2021-11-26|Univ Sevilla|ELECTRONIC DEVICE CALCULATING TRIGONOMETRIC FUNCTIONS AND USES OF THE SAME|
    ES2762747A1|2018-11-22|2020-05-25|Univ Sevilla|ELECTRONIC DEVICE CALCULATOR OF TRIGONOMETRIC FUNCTIONS |
    法律状态:
    2018-08-16| FG2A| Definitive protection|Ref document number: 2663168 Country of ref document: ES Kind code of ref document: B2 Effective date: 20180816 |
    优先权:
    申请号 | 申请日 | 专利标题
    ES201600865A|ES2663168B2|2016-10-10|2016-10-10|Digital electronic circuit for the calculation of sines and cosines of multiples of an angle|ES201600865A| ES2663168B2|2016-10-10|2016-10-10|Digital electronic circuit for the calculation of sines and cosines of multiples of an angle|
    PCT/ES2017/000123| WO2018104566A1|2016-10-10|2017-10-05|Digital electronic circuit for calculating sines and cosines of multiples of an angle|
    [返回顶部]